(load "ex1-27.scm")

(define (nontrivial-square-root? a n)
    (and (not (= a 1))
         (not (= a (- n 1)))
         (= 1 (remainder (square a) n))))

(define (expmod base exp m)
    (cond   ((= exp 0) 1)
            ((nontrivial-square-root? base m) 0)
            ((even? exp)
                (remainder  (square (expmod base (/ exp 2) m))
                            m))
            (else
                (remainder  (* base (expmod base (- exp 1) m))
                            m))))

(define (non-zero-random n)
    (let ((r (random n)))
        (if (not (= r 0))
            r
            (non-zero-random n))))

(define (Miller-Rabin-test n)
    (display n)
    (display ": ")
    (define (test-iter n times)
    (cond   ((= times 0) true)
            ((= (expmod (non-zero-random n) (- n 1) n) 1)
                (test-iter n (- times 1)))
            (else
                false)))
    (let ((times (ceiling (/ n 2))))
        (test-iter n times)))

(display "\n========================================\n")
(display (Miller-Rabin-test 561))
(newline)
(display (Miller-Rabin-test 1105))
(newline)
(display (Miller-Rabin-test 1729))
(newline)
(display (Miller-Rabin-test 2465))
(newline)
(display (Miller-Rabin-test 2821))
(newline)
(display (Miller-Rabin-test 6601))
(newline)
(display (Miller-Rabin-test 6602))
(display "\n========================================\n")